class MyQueue {
public:

    stack<int> stIn;
    stack<int> stOut;

    MyQueue() 
    {
        stIn = stack<int>();
        stOut = stack<int>();
    }
    
    void push(int x) 
    {
        stIn.push(x);
    }
    
    int pop() 
    {
        if(!stOut.empty())
        {
            int front = stOut.top();
            stOut.pop();
            return front;
        }

        // 走到这说明st2为空
        if(stIn.empty())
            return -1;

        while(!stIn.empty())
        {
            int front = stIn.top();
            stIn.pop();
            stOut.push(front);
        }

        int front = stOut.top();
        stOut.pop();
        return front;
    }
    
    int peek() 
    {
        if(!stOut.empty())
        {
            int front = stOut.top();
            return front;
        }
        
        if(stIn.empty())
            return -1;

        while(!stIn.empty())
        {
            int front = stIn.top();
            stIn.pop();
            stOut.push(front);
        }

        int front = stOut.top();
        return front;
    }
    
    bool empty() 
    {
        return stIn.empty() && stOut.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

class MyStack {
public:

    queue<int> q1;
    queue<int> q2; // 辅助队列 - 拷贝队列

    MyStack() {

    }
    
    void push(int x) 
    {
        q1.push(x);
    }
    
    int pop() 
    {
        while(q1.size() > 1)
        {
            int top = q1.front();
            q2.push(top);
            q1.pop();
        }

        int res = q1.front();
        q1.pop();

        q1 = q2;

        while(!q2.empty())
        {
            q2.pop();
        }

        return res;
    }
    
    int top() 
    {
        int front = pop();
        push(front);
        return front;
    }
    
    bool empty() 
    {
        return q1.empty() && q2.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

class Solution {
public:
    bool isValid(string s) 
    {
        // 定义栈结构，遇到左括号就入栈，遇到右括号就去栈顶进行比较
        stack<int> st;

        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                st.push(s[i]);
            }
            else
            {
                if(!st.empty() && leftOf(s[i]) == st.top())
                {
                    st.pop();
                }
                else 
                {
                    return false;
                }
            }
        }

        return st.empty();

    }

    char leftOf(char c)
    {
        if(c == ')') return '(';
        else if(c == ']') return '[';
        else return '{';
    }
};


class NumArray {
public:

    vector<int> preSum;

    NumArray(vector<int>& nums) 
    {
        int n = nums.size();
        preSum.resize(n + 1);
        // preSum[0] = 0;

        // preSum[i]表示的是nums[0,i-1]的和
        for(int i = 1; i <= n; i++)
        {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) 
    {
        return preSum[right + 1] - preSum[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */



